#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <cstdlib>
#include <cmath>

using namespace std;

typedef struct Node
{
    int data;
    struct Node *lchild;
    struct Node *rchild;
} BTNode;

int N;
vector<int> values(INT16_MAX >> 2);

void buildTree(BTNode *&node, int index)
{
    if (index > N || values[index] == -1)
    {
        node = nullptr;
        return;
    }
    node = (BTNode *)malloc(sizeof(BTNode));
    node->data = values[index];
    node->lchild = nullptr;
    node->rchild = nullptr;
    buildTree(node->lchild, 2 * index);
    buildTree(node->rchild, 2 * index + 1);
}

int deep(BTNode *&root)
{
    if (root == nullptr)
    {
        return 0;
    }
    int l = 0, r = 0;
    l = deep(root->lchild) + 1;
    r = deep(root->rchild) + 1;
    return max(l, r);
}

void preOrder(BTNode *&root)
{
    if (root)
    {
        cout << " " << root->data;
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}

void inOrder(BTNode *&root)
{
    if (root)
    {
        preOrder(root->lchild);
        cout << " " << root->data;
        preOrder(root->rchild);
    }
}

void postOrder(BTNode *&root)
{
    if (root)
    {
        preOrder(root->lchild);
        preOrder(root->rchild);
        cout << " " << root->data;
    }
}

void CreateByString(BTNode *&root, string &str)
{
    stack<BTNode *> S;

    BTNode *cur;
    char ch;
    int k;

    root = nullptr;

    for (auto &ch : str)
    {
        switch (ch)
        {
        case '(':
        {
            S.push(cur);
            k = 1;
            break;
        }
        case ')':
        {
            S.pop();
            break;
        }
        case ',':
        {
            k = 2;
            break;
        }
        default:
        {
            cur = (BTNode *)malloc(sizeof(BTNode));
            cur->data = ch;
            cur->lchild = nullptr;
            cur->rchild = nullptr;

            if (root == nullptr)
            {
                root = cur;
            }
            else
            {
                switch (k)
                {
                case 1:
                {
                    S.top()->lchild = cur;
                    break;
                }
                case 2:
                {
                    S.top()->rchild = cur;
                    break;
                }
                }
            }
        }
        }
    }
    // char ch;
    // cin >> ch;
    // if (ch == '#')
    // {
    //     root = nullptr;
    //     return;
    // }

    // root = (BTNode *)malloc(sizeof(BTNode));
    // root->data = ch;
    // S.push(root);
    // BTNode *cur = root;

    // while (!S.empty())
    // {
    //     cur = S.top();
    //     cur->lchild = nullptr;
    //     cur->rchild = nullptr;
    //     cin >> ch;
    //     if (ch == '(')
    //     {
    //         cur->lchild = (BTNode *)malloc(sizeof(BTNode));
    //         S.push(cur->lchild);
    //     }
    //     else if (ch == ',')
    //     {
    //         cur->rchild = (BTNode *)malloc(sizeof(BTNode));
    //         S.push(cur->rchild);
    //     }
    //     else if (ch == ')')
    //     {
    //         S.pop();
    //         S.pop();
    //         S.pop();
    //     }
    //     else if (ch == '#')
    //     {
    //         delete cur;
    //         S.pop();
    //         cur = S.top();
    //         if (cur->rchild == nullptr)
    //         {
    //             cur->lchild = nullptr;
    //         }
    //         else
    //         {
    //             cur->rchild = nullptr;
    //         }
    //     }
    //     else
    //     {
    //         cur->data = ch;

    //     }
    // }
}

void inOrder2(BTNode *&root)
{
    stack<BTNode *> S;
    BTNode *cur = root;

    while (cur != nullptr || !S.empty())
    {
        // while (cur->lchild != nullptr)
        // {
        //     S.push(cur);
        //     cur = cur->lchild;
        // }

        // cout << cur->data - '0' << ' ';

        // if (!S.empty())
        // {
        //     cur = S.top();
        //     cout << cur->data - '0' << ' ';
        //     S.pop();
        //     cur = cur->rchild;
        // }
        // else
        // {
        //     cur = cur->rchild;
        // }
        if (cur)
        {
            S.push(cur);
            cur = cur->lchild;
        }
        else {
            cur = S.top();
            S.pop();
            cout << cur->data - '0' << " ";
            cur = cur->rchild;
        }
    }
}

int main(void)
{
    /**
     * @brief 问题一
     *
     */
    BTNode *tree = nullptr;
    cout << "输入树的大小：" << endl;
    cin >> N;
    values.resize(N + 1, -1);
    int i = 1, temp;
    while (cin >> temp)
    {
        if (temp == -1 || i > N)
        {
            i--;
            break;
        }
        values[i] = temp;
        i++;
        // cout << i << endl;
    }

    buildTree(tree, 1);
    preOrder(tree);
    cout << endl;
    inOrder(tree);
    cout << endl;
    postOrder(tree);
    cout << endl;
    cout << deep(tree);
    cout << endl;
    cout << "----------------------------" << endl;

    /**
     * @brief 问题二
     * 
     */
    BTNode *tree2 = nullptr;
    string s;
    cin >> s;
    // s = "1(2,3(4(6,),5))"
    CreateByString(tree2, s);
    inOrder2(tree2);
    // inOrder(tree2);
    return 0;
}